---
title: "调手表"
created: 2025-11-28
tags:
  - 算法
---

# 调手表

## 题目 [调手表](https://www.lanqiao.cn/paper/3851/problem/230/)

![[image-02a5cc67.png]]

## 思路分析

感觉是bfs 求某点到任意点的最短距离 的最大值

但是 每一步的选法是不定的 即 可以走1步 也可以走k步 这里涉及一个选择的问题

也就是说 在这个图里面 权并不是固定为1的

但这个数据范围有些过大 感觉最短路……

事实是居然可以全过 蓝桥杯啊蓝桥杯

或者好像还可以用跳台阶的思路

从原本的 到第n阶至少需要多少步 变成到任意阶至少需要多少步 然后取一个max 其实就是最后取个max(f[1]~f[n])

照思路来写的话 是这样

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e5+10;
int f[N];//到i点需要的最小步数  从两种可能的来 (i+n-1)%n点走1步 或者(i+n-k)%n点走k步
int n,k;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	memset(f,0x3f,sizeof f);//因为求最小步数 所以初始化为最大值 便于转移
	f[0]=0,f[1]=1,f[k]=1;
	for(int i=0;i<n;i++){
		f[i]=min({f[i],f[(i+n-1)%n]+1,f[(i+n-k)%n]+1});
	}
	int res=-1;
	for(int i=0;i<n;i++){
		res=max(res,f[i]);
	}
	cout<<res;
	return 0;
}
```

只能过五个

有个问题是  时间是环状的 需要处理循环依赖和周期性的问题

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int f[N];
int n,k;

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >> n >> k;
    memset(f, 0x3f, sizeof(f));
    f[0]=0,f[1]=1,f[k]=1;

    // 由于环形结构，可能需要多次遍历来确保所有状态达到最优
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; i++) {
            int new_fi=min(f[(i+n-1)%n],f[(i+n-k)%n])+1;
            if (new_fi < f[i]) {
                f[i] = new_fi;
                changed = true;
            }
        }
    }

    int res=-1;
    for(int i=0;i<n;i++){
      res=max(res,f[i]);
    }
    cout<<res;

    return 0;
}
```

很容易忽略这一点 害

这怎么说呢 这种题目在事先不知道的情况下 能用bfs但是没把握全过 可dp一不小心可能满盘皆输

太抽象了

![[image-361ff683.png]]

有这么简单？ 4道dfs、bfs 真练好暴力蓝桥杯随便打啊

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=1e5+10;
int d[N];
int n,k,res=-1;

int bfs(int u){
	queue<int> q;
	memset(d,-1,sizeof d);
	q.push(u);
	d[u]=0;
	while(!q.empty()){
		int cur=q.front();q.pop();
		res=max(res,d[cur]);
		if(d[(cur+1)%n]==-1){
			d[(cur+1)%n]=d[cur]+1;
			q.push((cur+1)%n);
		}
		if(d[(cur+k)%n]==-1){
			d[(cur+k)%n]=d[cur]+1;
			q.push((cur+k)%n);
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	cout<<bfs(0);
	return 0;
}
```

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int f[N];
int n,k;

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >> n >> k;
    memset(f, 0x3f, sizeof(f));
    f[0]=0,f[1]=1,f[k]=1;

    // 由于环形结构，可能需要多次遍历来确保所有状态达到最优
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; i++) {
            int new_fi=min(f[(i+n-1)%n],f[(i+n-k)%n])+1;
            if (new_fi < f[i]) {
                f[i] = new_fi;
                changed = true;
            }
        }
    }

    int res=-1;
    for(int i=0;i<n;i++){
      res=max(res,f[i]);
    }
    cout<<res;

    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[格雷码|格雷码]] 🏠 [[00-冲刺国赛]] ➡️ [[搭积木|搭积木]]